#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
根节点为0
对于二叉树，有第一个叶子节点为len/2,最后以恶搞非叶子节点为len/2-1.
完全二叉树最后一层的节点数为(len+1)/2,故最后一个非叶子节点为len/2-1.
若当前节点为i,则左子节点为2*i+1，右子节点为2*i+2


构建大根堆可以采用递归的方式，先找到最后一个非叶子节点，从后往前遍历,将比该节点大的子节点与该节点交换，
再保持交换后的子节点与它的子节点保持大根堆,以此类推直至根节点。
*/



void buildHeap(vector<int> &v,int start,int end)
{
    //遍历start的子节点，找到最大子节点若大于父节点，则交换,交换后需要维护下面的节点保持大根堆。
    //start的左子节点为2*start+1,右子节点为2*start+2
    int parent=start;
    for(int i=start*2+1;i<=end;i=i*2+1)
    {
        //找到最大子节点，子节点大于父节点，则交换
        if(i+1<=end && v[i]<v[i+1])
            i++;
        if(v[i]>v[parent])
            swap(v[i],v[parent]);
        //将下次的父节点更新为当前进行交换的子节点
        parent=i;
    }
    // cout<<"after build heap:"<<endl;
    // for(int i=0;i<v.size();i++)
    // {
    //     cout<<v[i]<<" ";
    // }
    // cout<<endl;
}


void heapSort(vector<int>& v)
{
    //首先先构建大根堆,先找到最后一个非叶子节点，从后往前遍历,直至根节点。
    //对于二叉树有第一个叶子节点为len/2,故最后一个非叶子节点为len/2-1.
    //完全二叉树最后一层的节点数一定是(len+1)/2,故最后一个非叶子节点为len/2-1.
    for(int i=v.size()/2-1;i>=0;i--)
    {
        buildHeap(v,i,v.size()-1);
    }
    cout<<"after built big heap:"<<endl;
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
    //将跟节点（最大元素）换到最后一个位置，然后对剩余的元素进行堆排序。
    for(int i=0;i<v.size();i++)
    {
        swap(v[0],v[v.size()-1-i]);
        buildHeap(v,0,v.size()-2-i);
        cout<<"after sorts"<<i<<":"<<endl;
        for(int i=0;i<v.size();i++)
        {
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }
}
int main()
{
    cout<<"Enter the numbers:"<<endl;
    vector<int> v;
    int n;
    while(n!=-1)
    {
        cin>>n;
        v.push_back(n);
    }
    v.pop_back();
    heapSort(v);
    return 0;
}